package middle;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import middle.Solution_341.IntegerC;

public class Solution_437 {

    public static void main(String[] args) {
        Solution_437 model = new Solution_437();

        // [1000000000,1000000000,null,294967296,null,1000000000,null,1000000000,null,1000000000]
        //0
        TreeNode root = new TreeNode(1000000000);
        root.left = new TreeNode(1000000000);
        root.left.left = new TreeNode(294967296);
        root.left.left.left = new TreeNode(1000000000);
        root.left.left.left.left = new TreeNode(1000000000);
        root.left.left.left.left.left = new TreeNode(1000000000);
        System.out.println(model.pathSum(root, 0));

//        TreeNode root = new TreeNode(1);
//        root.left = new TreeNode(2);
//        root.left.left = new TreeNode(3);
//        root.left.left.left = new TreeNode(4);
//        root.left.left.left.left = new TreeNode(5);
//        System.out.println(model.pathSum(root, 3));

//        TreeNode root = new TreeNode(10);
//        root.left = new TreeNode(5);
//        root.left.left = new TreeNode(3);
//        root.left.left.left = new TreeNode(3);
//        root.left.left.right = new TreeNode(-2);
//        root.left.right = new TreeNode(2);
//        root.left.right.right = new TreeNode(1);
//        root.right= new TreeNode(-3);
//        root.right.right= new TreeNode(11);
//        System.out.println(model.pathSum(root, 8));
        System.out.println();
    }

    private int count = 0;

    public int pathSum(TreeNode root, int targetSum) {
        count = 0;
        dps_dps(root, targetSum);
        return count;
    }

    public void dps_dps(TreeNode root, long targetSum) {
        dps(root, targetSum);
        if (root != null) {
            dps_dps(root.left, targetSum);
            dps_dps(root.right, targetSum);
        }
    }

    private void dps(TreeNode node, long val) {
        if (node != null) {
            if (node.val == val) {
                count++;
            }
            dps(node.left, val - node.val);
            dps(node.right, val - node.val);
        }
    }

    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
